//给定两个二叉树，编写一个函数来检验它们是否相同。 
//
// 如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。 
//
// 示例 1: 
//
// 输入:       1         1
//          / \       / \
//         2   3     2   3
//
//        [1,2,3],   [1,2,3]
//
//输出: true 
//
// 示例 2: 
//
// 输入:      1          1
//          /           \
//         2             2
//
//        [1,2],     [1,null,2]
//
//输出: false
// 
//
// 示例 3: 
//
// 输入:       1         1
//          / \       / \
//         2   1     1   2
//
//        [1,2,1],   [1,1,2]
//
//输出: false
// 
// Related Topics 树 深度优先搜索 
// 👍 407 👎 0

package leetcode.editor.cn;

import common.bean.TreeNode;

/**
 * Java：相同的树
 *
 * @author changgui
 */
@SuppressWarnings("all")
public class P100_SameTree {
    public static void main(String[] args) {
        Solution solution = new P100_SameTree().new Solution();
        // TODO 此处开始你的表演

    }

    //leetcode submit region begin(Prohibit modification and deletion)

    /**
     * 递归
     * 时间复杂度 O(n)
     */
    class Solution {
        public boolean isSameTree(TreeNode t1, TreeNode t2) {
            if(t1 == null && t2 == null) {
                return true;
            }
            if(t1 == null || t2 == null) {
                return false;
            }
            if(t1.val != t2.val) {
                return false;
            }
            return isSameTree(t1.left, t2.left) && isSameTree(t1.right, t2.right);
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)

}
